Shareware Grab Bag/Shareware Grab Bag.iso/050/madtrb10.arc/STACK.PAS

Pascal/Delphi Source File | 1985-12-08 | 25.8 KB | 546 lines

Program Stack;

{ *************************************************************************** }
{ *                                                                         * }
{ *          POLISH POSTFIX NOTATION EXPRESSION EVALUATION PROGRAM          * }
{ *                    using a Stack Data Structure                         * }
{ *                             Program #4                                  * }
{ *                                                                         * }
{ *                     Class: CS 367     Section: 4                        * }
{ *                         Instructor: Wiegand                             * }
{ *                                                                         * }
{ *                       Written by Chris Maeder                           * }
{ *                Edited and Compiled using Turbo Pascal                   * }
{ *                            on an IBM PC                                 * }
{ *                                                                         * }
{ *   DEFINITION:                                                           * }
{ *        A stack is a data structure which exhibits last-in/first-out     * }
{ *        behavior.  Elements are added to the top of the stack and only   * }
{ *        the top-most element element can be removed.  When the top-most  * }
{ *        element is removed then the second top-most element can be       * }
{ *        removed.  The operation of adding an element to the top of the   * }
{ *        stack is called Push.  That operation of removing the top-most   * }
{ *        element from the stack is called Pop.                            * }
{ *                                                                         * }
{ *   ALGORITHM:                                                            * }
{ *        A stack is implimented through the use of pointers, creating a   * }
{ *        linked list of elements with a pointer pointing to the top-most  * }
{ *        element.                                                         * }
{ *                                                                         * }
{ *                        STACK                                            * }
{ *                                                                         * }
{ *                     ------------                                        * }
{ *                    | Operand #1 |  <-----Top Pointer                    * }
{ *                     ------------                                        * }
{ *                          |                                              * }
{ *                          V                                              * }
{ *                     ------------                                        * }
{ *                    | Operand #2 |                                       * }
{ *                     ------------                                        * }
{ *                          |                                              * }
{ *                          V                                              * }
{ *                     ------------                                        * }
{ *                    | Operand #3 |                                       * }
{ *                     ------------                                        * }
{ *                          |                                              * }
{ *                          V                                              * }
{ *                     ------------                                        * }
{ *                    | Operand #4 |                                       * }
{ *                     ------------                                        * }
{ *                          |                                              * }
{ *                          V                                              * }
{ *                         Nil                                             * }
{ *                                                                         * }
{ *        A stack is used to evaluate expressions written in Polish        * }
{ *        postfix notation (PPN).  Operands are pushed onto the stack      * }
{ *        until a operator is received.  Then the stack is popped twice    * }
{ *        and the two values are operated upon by the operator and the     * }
{ *        result is pushed back onto the top of the stack.  When the       * }
{ *        expression is finished being evaluated the final result is       * }
{ *        popped off of the stack and then printed.                        * }
{ *                                                                         * }
{ *        If an error is encountered during the evaluation of the          * }
{ *        expression an error message is printed and the next expression   * }
{ *        is then evaluated.                                               * }
{ *                                                                         * }
{ *        Valid mathematical operators are:                                * }
{ *                                                                         * }
{ *                      Addition                                           * }
{ *                      Subtraction                                        * }
{ *                      Multiplication                                     * }
{ *                      Division                                           * }
{ *                      Exponentiation                                     * }
{ *                                                                         * }
{ *   PURPOSE:                                                              * }
{ *        1. Print program heading.                                        * }
{ *        2. Evaluate Polish postfix notation (PPN) expression using a     * }
{ *           stack data structure.                                         * }
{ *        3. Implement the stack data structure using pointers.            * }
{ *        4. Operate on the stack data structure with the following        * }
{ *           functions and procedures.                                     * }
{ *           a. CreateStack-create a stack, setting top pointer to Nil.    * }
{ *           b. Push-add an element to top of stack.                       * }
{ *           c. EmptyStack-determine if the stack is empty.                * }
{ *           d. Pop-remove an element from the top of the stack.           * }
{ *           e. DeleteStack-remove all elements in a stack, setting top    * }
{ *              pointer to Nil.                                            * }
{ *        5. Check for malformed PPN expressions.                          * }
{ *                                                                         * }
{ *   INPUT/OUTPUT:                                                         * }
{ *        1. Print program heading.                                        * }
{ *        2. Read the PPN expression out of the data file.                 * }
{ *           a. Echo print the PPN expression.                             * }
{ *        3. Starting from the left, pick off entries out of the PPN       * }
{ *           expression.  Entries are assumed to be seperated by a         * }
{ *           single blank.                                                 * }
{ *           a. Operand entry                                              * }
{ *              i.   Push operand onto top of stack.                       * }
{ *           b. Operator entry                                             * }
{ *              i.   Pop the stack twice to get two operands.              * }
{ *              ii.  Using the operator, operate on the two operands.      * }
{ *              iii. Push the result back onto the stack.                  * }
{ *        4. After the expression has been evaluated, print the result     * }
{ *           of the expression.                                            * }
{ *        5. Otherwise print an error message if it was found that         * }
{ *           a. Invalid character in the expression.                       * }
{ *           b. Malformed PPN expression.                                  * }
{ *                                                                         * }
{ *************************************************************************** }

Const
  MAX_ENTRY_SIZE=80;                             { maximum size of the PPN expression }
  MAX_NEG_INT=-32767;                            { maximum negative integer, used in flagging an error }
  FILE_NAME='Stack.Fil';                         { input file name which contains PPN expressions requiring evaluation }
  L_PRINT=False;                                 { a boolean used to control the re-direction of output to the printer }

Type
  StackElementPtr=^StackElementType;             { a pointer which points to the data record type 'StackElementType' }
  StackElementType=                              { stack element data record type }
    Record
      NumericData:Real;                          { field used to store real numbers }
      NextElement:StackElementPtr;               { field used to store next element pointer }
    End; { StackElementType }
  EntryString=String[MAX_ENTRY_SIZE];            { a string type used to store expressions and entries }

Var
  Error:Boolean;                                 { an error flag which is used to tell the program that there is
                                                   something wrong with the PPN expression }
  Top:StackElementPtr;                           { a pointer used to point to the top of the stack }
  HoldPtr:Integer;                               { a temporary pointer used in the re-directing of the output
                                                   from the screen to the printer }



Procedure PrintHeading;

{ This procedure prints a heading for the program. }

Begin   { PrintHeading }
  WriteLn;
  WriteLn('POLISH POSTFIX NOTATION EXPRESSION EVALUATION PROGRAM');
  WriteLn;
End;    { PrintHeading }



Procedure RemoveFirstEntryFromString(Var Text:EntryString);

{ This procedure removes the first text entry from the passed text string and
  returns the new truncated text string.  The text entries in the passed text
  string are assumed to be delinated by one space.  See the following
  example.

         Passed:    Entry1  Entry2  Entry3
         Returned:  Entry2  Entry3                      }

Begin   { RemoveFirstEntryFromString }
  If Pos(' ',Text)=0 Then
    Text:=''
  Else
    Text:=Copy(Text,(Pos(' ',Text)+1),(Length(Text)-Pos(' ',Text)));
End;    { RemoveFirstEntryFromString }



Procedure ReturnFirstEntryFromString(Var Text:EntryString);

{ This procedure removes the first text entry from the passed text string and
  returns the first text entry.  The text entries in the passed text string
  are assumed to be delinated by one space.  See the following example.

         Passed:    Entry1  Entry2  Entry3
         Returned:  Entry1                              }

Begin   { ReturnFirstEntryFromString }
  If Pos(' ',Text)<>0 Then
    Text:=Copy(Text,1,(Pos(' ',Text)-1));
End;    { ReturnFirstEntryFromString }



Procedure DetermineEntryInExpression(Var Expression,Entry:EntryString);

{ The entries in the passed PPN expression are assumed to be delinated by one
  space.  This procedure removes the front lying entry from the expression and
  returns the now shortened expression and the expression's entry to the
  calling routine.  An example follows:

        Passed Values
          Expression : Entry1 Entry2 Entry3
          Entry      :

        Returned Values
          Expression : Entry2 Entry3
          Entry      : Entry1

  If the returned expression is empty then a blank entry is returned. }

Begin   { DetermineEntryInExpression }
  Entry:=Expression;
  ReturnFirstEntryFromString(Entry);
  RemoveFirstEntryFromString(Expression);
End;    { DetermineEntryInExpression }



Procedure CreateStack(Var StackTopPtr:StackElementPtr);

{ This procedure is used at program start-up to initialize the stack's top
  pointer to nil.  This corresponds to the stack being empty. }

Begin   { CreateStack }
  Top:=Nil;
End;    { CreateStack }




Procedure DisposeStack(Var StackTopPtr:StackElementPtr);

{ This procedure is used after a PPN expression has been ( or was tried to
  be ) evaluated.  It removes any remaining stack elements and sets the
  top of the stack pointer to point to nil. }

Var
  TempStackElementPtr:StackElementPtr;           { a temporary pointer to a stack element }

Begin   { DisposeStack }
  While StackTopPtr<>Nil Do
    Begin
      TempStackElementPtr:=StackTopPtr;          { temporarily save reference to top stack element }
      StackTopPtr:=StackTopPtr^.NextElement;     { have the top stack pointer point to the next element in the stack }
      Dispose(TempStackElementPtr);              { dispose of the previous top stack pointer }
    End; { While StackTopPtr }
End;    { DiposeStack }



Function EmptyStack(StackTopPtr:StackElementPtr):Boolean;

{ This function is used to check if the present stack is empty.  If the stack
  is empty this function returns as true, else it returns as false. }

Begin   { EmptyStack }
  If StackTopPtr=Nil Then
    EmptyStack:=True                             { the present stack is empty }
  Else
    EmptyStack:=False;                           { the present stack is not empty }
End;    { EmptyStack }



Function LegalNumericEntry(StringEntry:EntryString):Boolean;

{ This function determines if the passed string entry is a legal real or
  integer number.  If the passed string entry is legal this funstion returns
  as true, else it returns as false. }

Var
  NumericEntry:Real;                             { used to temporarily store the converted string entry }
  ErrorCode:Integer;                             { an error code used in the string procedure 'Val' }

Begin   { LegalNumericEntry }
  Val(StringEntry,NumericEntry,ErrorCode);       { convert the string entry into a numeric entry.  Error code is set to the
                                                   position of the first character in error. }
  If ErrorCode=0 Then
    LegalNumericEntry:=True                      { legal numeric entry }
  Else
    LegalNumericEntry:=False;                    { illegal numeric entry }
End;    { LegalNumericEntry }



Procedure Push(NumericStackEntry:Real);

{ This procedure first transfers the number into a newly stack
  element record.  Finally it adds this stack element to the top of the
  present stack while resetting the top stack pointer to point to it. }

Var
  StackElement:StackElementPtr; { a pointer to a newly formed stack element }

Begin   { Push }
  New(StackElement);                             { create a new record to store a pushed stack element }
  StackElement^.NumericData:=NumericStackEntry;  { transfer numeric stack entry into stack element record }
  StackElement^.NextElement:=Top;                { insert stack element into the top of the present stack }
  Top:=StackElement;                             { reset top stack pointer to point to top of the stack }
End;    { Push }



Procedure Pop(Var NumericStackEntry:Real);

{ This procedure removes an element from the top of the stack and passes the
  element back to the calling routine.  If the stack happens to be empty then
  the procedure  flags the error by returning an empty element (equal to
  negative maximum integer).  This then tells the calling routine that there
  is an error in the PPN expression. }

Const
  EMPTY=MAX_NEG_INT;

Var
  TempStackElementPtr:StackElementPtr;           { a temporary pointer to the stack element that has just been taken off
                                                   the top of the stack }

Begin   { Pop }
  If Not EmptyStack(Top) Then                    { check if the stack is not empty }
    Begin
      NumericStackEntry:=Top^.NumericData;       { pull numeric data out of the topmost stack element }
      TempStackElementPtr:=Top;                  { temporarily save reference to top stack element }
      Top:=Top^.NextElement;                     { have the top stack pointer point to the next element in the stack }
      Dispose(TempStackElementPtr);              { dispose of the previous top stack element }
    End { if Not EmptyStack }
  Else
    NumericStackEntry:=EMPTY;                    { set a flag to tell the calling routine that procedure could not remove
                                                   an element off of the empty stack }
End;    { Pop }



Procedure Addition;

{ This procedure pops the two topmost elements from the stack, adds them
  together and pushes the result back onto the stack.  If this procedure
  detects that an error occured when trying to pop the elements off of the
  stack, it flags an error and prints the appropriate error message. }

Var
  FirstEntry,SecondEntry:Real;                   { used to stare the elements removed from the top of the stack }

Begin   { Addition }
  Pop(FirstEntry);                               { remove topmost element from the stack }
  Pop(SecondEntry);                              { remove second topmost element from the stack }
  If (FirstEntry<>MAX_NEG_INT) And (SecondEntry<>MAX_NEG_INT) Then { check for error in popping elements off of stack }
    Push(SecondEntry+FirstEntry)
  Else
    Error:=True;
End;    { Addition }



Procedure Subtraction;

{ This procedure pops the two topmost elements from the stack, subtracts the
  first entry from the second entry and pushes the result back onto the stack.
  If this procedure detects that an error occured when trying to pop the
  elements off of the stack, it flags an error and prints the appropriate
  error message. }

Var
  FirstEntry,SecondEntry:Real;                   { used to stare the elements removed from the top of the stack }

Begin   { Subtraction }
  Pop(FirstEntry);                               { remove topmost element from the stack }
  Pop(SecondEntry);                              { remove second topmost element from the stack }
  If (FirstEntry<>MAX_NEG_INT) And (SecondEntry<>MAX_NEG_INT) Then { check for error in popping elements off of stack }
    Push(SecondEntry-FirstEntry)
  Else
    Error:=True;
End;    { Subtraction }



Procedure Multiplication;

{ This procedure pops the two topmost elements from the stack, multiplies them
  together and pushes the result back onto the stack.  If this procedure
  detects that an error occured when trying to pop the elements off of the
  stack, it flags an error and prints the appropriate error message. }

Var
  FirstEntry,SecondEntry:Real;                   { used to stare the elements removed from the top of the stack }

Begin   { Multiplication }
  Pop(FirstEntry);                               { remove topmost element from the stack }
  Pop(SecondEntry);                              { remove second topmost element from the stack }
  If (FirstEntry<>MAX_NEG_INT) And (SecondEntry<>MAX_NEG_INT) Then { check for error in popping elements off of stack }
    Push(SecondEntry*FirstEntry)
  Else
    Error:=True;
End;    { Multiplication }



Procedure Division;

{ This procedure pops the two topmost elements from the stack, divides the
  first entry into the second entry and pushes the result back onto the stack.
  If this procedure detects that an error occured when trying to pop the
  elements off of the stack, it flags an error and prints the appropriate
  error message. }

Var
  FirstEntry,SecondEntry:Real;                   { used to stare the elements removed from the top of the stack }

Begin   { Division }
  Pop(FirstEntry);                               { remove topmost element from the stack }
  Pop(SecondEntry);                              { remove second topmost element from the stack }
  If (FirstEntry<>MAX_NEG_INT) And (SecondEntry<>MAX_NEG_INT) Then { check for error in popping elements off of stack }
    Push(SecondEntry/FirstEntry)
  Else
    Error:=True;
End;    { Division }



Procedure Exponentiation;

{ This procedure pops the two topmost elements from the stack, raises the
  second entry to the power of the first entry and pushes the result back onto
  the stack.  If this procedure detects that an error occured when trying to
  pop the elements off of the stack, it flags an error and prints the
  appropriate error message. }

Var
  FirstEntry,SecondEntry:Real;                   { used to stare the elements removed from the top of the stack }

Begin   { Exponentiation }
  Pop(FirstEntry);                               { remove topmost element from the stack }
  Pop(SecondEntry);                              { remove second topmost element from the stack }
  If (FirstEntry<>MAX_NEG_INT) And (SecondEntry<>MAX_NEG_INT) Then { check for error in popping elements off of stack }
    Push(Exp(FirstEntry*Ln(SecondEntry)))
  Else
    Error:=True;
End;    { Exponentiation }



Procedure WriteResultOfExpression;

{ This procedure writes the evaluation results from the PPN expression. }

Begin   { WriteResultOfExpression }
  WriteLn;
  WriteLn('The result of the above expression is : ',Top^.NumericData);
End;    { WriteResultOfExpression }



Procedure Evaluate_PPN_Expression(Expression:EntryString);

{ This procedure controls the evaluation of the passed PPN expression.  It
  passes control to specific procedures when a valid operator is evaluated
  within the expression.  When a valid operand is evaluated within the
  expression it is pushed onto the stack.

  Valid operators are +,-,*,/, and ^.  A valid operand is any real or integer
  number with a maximum of 10 places including the decimal point if one
  exists.  Blanks seperate operators from operands.  All arithmetic is real.
  A negative number has a minus sign immediately preceeding it.

  Examples of PPN expressions are:

        PPN Expression               Equivalent Algebraic Expression
        --------------               -------------------------------
             2 5 -                                2-5

             6 2 /                                6/2
                                                   2
             4 2 ^                                4     }

Var
  Entry:EntryString;                             { used to store an entry from within the PPN expression }
  NumericStackEntry:Real;                        { used to store the converted string stack entry }
  ErrorCode:Integer;                             { an error code used in the string procedure 'Val' }

Begin   { Evaluate_PPN_Expression }
  Error:=False;                                  { set error flag to false }
  DetermineEntryInExpression(Expression,Entry);  { pull first entry out of the PPN expression }
  While (Entry<>'') And Not Error Do
    Begin  { determine entry }
      If (Entry='+') Or (Entry='-') Or (Entry='*') Or (Entry='/') Or (Entry='^') Then { check for valid operator }
        Case Entry Of                            { perform operation }
          '+' : Addition;
          '-' : Subtraction;
          '*' : Multiplication;
          '/' : Division;
          '^' : Exponentiation;
        End { Case Entry }
      Else                                       { perform operation }
        If LegalNumericEntry(Entry) Then
          Begin
            Val(Entry,NumericStackEntry,ErrorCode); { convert the StringStackEntry into a NumericStackEntry. ErrorCode is
                                                      set to the position of the first character in error. }
            Push(NumericStackEntry);             { push valid operand onto stack }
          End { If LegalNumericEntry }
        Else                                     { malformed PPN expression }
          Error:=True;
      DetermineEntryInExpression(Expression,Entry);
    End; { While (Entry }
    If Error Or (Top^.NextElement<>Nil) Then
      Begin
        WriteLn;
        WriteLn('There was an error detected in the above expression.');
        Error:=True;
      End; { If Top^.NextElement }
  If Not Error Then
    WriteResultOfExpression;
  DisposeStack(Top);
End;    { Evaluate_PPN_Expression }



Procedure ReadInputFile;

{ This procedure reads expressions written in Polish postfix notation (PPN)
  from the declared file.  Each file entry in the declared file is a complete
  PPN expression.

  Once the PPN entry is read from the file the entry is then passed to a
  procedure which evaluates and prints the results of the PPN expression. }

Var
  DataFile:Text;                                 { text file }
  FileEntry:EntryString;                         { a string used to store the file entry for evaluation }

Begin   { ReadInputFile }
  Assign(DataFile,FILE_NAME);                    { assign to a disk file }
  Reset(DataFile);                               { open the file for reading }
  Repeat                                         { read in the file entries }
    ReadLn(DataFile,FileEntry);
    WriteLn;
    WriteLn;
    WriteLn;
    WriteLn;
    WriteLn('Polish postfix notation expression : ');
    WriteLn;
    WriteLn('     ',FileEntry);
    Evaluate_PPN_Expression(FileEntry);          { pass PPN expression to be evaluated }
  Until Eof(DataFile);
  Close(DataFile);                               { close the disk file }
End;    { ReadInputFile }



Begin   { Main program }
  HoldPtr:=ConOutPtr;                            { temporarily store current output address }
  If L_PRINT Then
    ConOutPtr:=LstOutPtr;                        { re-direct output to the printer }
  PrintHeading;
  CreateStack(Top);
  ReadInputFile;
  ConOutPtr:=HoldPtr;                            { reset output device address }
End.    { Main program }